#include <cmath>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;


class BucketSort {
public:
    static void bucketSort(int *array, int length) {
        int min_value;
        int max_value;

        bool flag = true;
        for (int i = 0; i < length; i++) {
            if (flag) {
                min_value = max_value = array[i];
                flag = false;

            } else {
                min_value = min(min_value, array[i]);
                max_value = max(max_value, array[i]);
            }
        }

        int bucket_size = sqrt(max_value - min_value) + 1;
        int bucket_count = (max_value - min_value) / bucket_size + 1;

        vector<int> bucket[bucket_count];

        for (int i = 0; i < length; ++i) {
            int index = min(bucket_count - 1, (array[i] - min_value) / bucket_size + 1);

            bucket[index].push_back(array[i]);
        }

        for (int i = 0; i < bucket_count; ++i) {
            sort(bucket[i].begin(), bucket[i].end());
        }

        int count = 0;
        for (int i = 0; i < bucket_count; ++i) {
            for (int const &value : bucket[i]) {
                array[count++] = value;
            }
        }
    }
};